/*
 * @lc app=leetcode.cn id=870 lang=cpp
 *
 * [870] 优势洗牌
 *
 * https://leetcode-cn.com/problems/advantage-shuffle/description/
 *
 * algorithms
 * Medium (44.82%)
 * Likes:    176
 * Dislikes: 0
 * Total Accepted:    20.9K
 * Total Submissions: 46.1K
 * Testcase Example:  '[2,7,11,15]\n[1,10,4,11]'
 *
 * 给定两个大小相等的数组 A 和 B，A 相对于 B 的优势可以用满足 A[i] > B[i] 的索引 i 的数目来描述。
 *
 * 返回 A 的任意排列，使其相对于 B 的优势最大化。
 *
 *
 *
 * 示例 1：
 *
 * 输入：A = [2,7,11,15], B = [1,10,4,11]
 * 输出：[2,11,7,15]
 *
 *
 * 示例 2：
 *
 * 输入：A = [12,24,8,32], B = [13,25,32,11]
 * 输出：[24,32,8,12]
 *
 *
 *
 *
 * 提示：
 *
 *
 * 1 <= A.length = B.length <= 10000
 * 0 <= A[i] <= 10^9
 * 0 <= B[i] <= 10^9
 *
 *
 */

// @lc code=start
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
class Solution
{
public:
    vector<int> advantageCount(vector<int> &nums1, vector<int> &nums2)
    {
        int n = nums1.size();
        vector<int> ans(n, -1);
        priority_queue<pair<int, int>, vector<pair<int, int>>> q1;
        priority_queue<pair<int, int>, vector<pair<int, int>>> q2;
        for (int i = 0; i < n; ++i)
        {
            q1.push(make_pair(nums1[i], i));
            q2.push(make_pair(nums2[i], i));
        }
        while (!q2.empty())
        {
            if (q1.top().first > q2.top().first)
            {
                ans[q2.top().second] = q1.top().first;
                q1.pop();
                q2.pop();
            }
            else
            {
                q2.pop();
            }
        }
        for (int i = 0; i < n; ++i)
        {
            if (ans[i] < 0)
            {
                if (!q1.empty())
                {
                    ans[i] = q1.top().first;
                    q1.pop();
                }
            }
        }
        return ans;
    }
};
// @lc code=end
